# 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，
# 采取相反方式重构得到原数据。
#  请设计一个算法来实现二叉树的序列化与反序列化。
#  这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
#  提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的
# 方法解决这个问题。
#
#  示例 1：
# 输入：root = [1,2,3,null,null,4,5]
# 输出：[1,2,3,null,null,4,5]
#  示例 2：
# 输入：root = []
# 输出：[]
#
#  示例 3：
# 输入：root = [1]
# 输出：[1]
#
#  示例 4：
# 输入：root = [1,2]
# 输出：[1,2]
from com.example.tree.tree_node import TreeNode


# BFS方式
class Codec:
    def serialize(self, root: TreeNode) -> str:
        """
        Encodes a tree to a single string.
        :param root: TreeNode
        :return: encoded string
        """
        if not root:
            return '[]'
        res, queue = [], [root]
        while queue:
            tmp = queue[0]
            if tmp:
                res.append(tmp.val)
                queue.append(tmp.left)
                queue.append(tmp.right)
            else:
                res.append('null')
            del queue[0]
        return '[' + ','.join(str(s) for s in res) + ']'  # 最后可以不拼接左右中括号

    def deserialize(self, data) -> TreeNode:
        """
        Decodes your encoded data to tree.

        :param data: tree string
        :return: TreeNode
        """
        if data == '[]':
            return None
        nodeVals = data[1:-1].split(',')
        root = TreeNode(int(nodeVals[0]))
        queue = [root]
        i = 1
        while queue:
            tmp = queue[0]
            if nodeVals[i] != 'null':
                tmp.left = TreeNode(int(nodeVals[i]))
                queue.append(tmp.left)
            i += 1
            if nodeVals[i] != 'null':
                tmp.right = TreeNode(int(nodeVals[i]))
                queue.append(tmp.right)
            i += 1
            del queue[0]
        return root


# DFS方式(前序方式)
class Codec2:
    def serialize(self, root: TreeNode) -> str:
        """
        Encodes a tree to a single string.
        :param root: TreeNode
        :return: encoded string
        """
        res = []
        def dfs(root: TreeNode) -> None:
            if not root:
                res.append('null')
                return

            res.append(str(root.val))

            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return '[' + ','.join(res) + ']'

    def deserialize(self, data) -> TreeNode:
        """
        Decodes your encoded data to tree.

        :param data: tree string
        :return: TreeNode
        """
        nodeVals = data[1:-1].split(',')

        def dfs() -> TreeNode:
            if nodeVals[0] == 'null':
                del nodeVals[0]
                return None

            root = TreeNode(int(nodeVals[0]))
            del nodeVals[0]

            root.left = dfs()
            root.right = dfs()

            return root

        return dfs()


if __name__ == "__main__":
    # ser = Codec()
    # deser = Codec()
    # root = TreeNode(1)
    # root.left, root.right = TreeNode(2), TreeNode(3)
    # root.right.left, root.right.right = TreeNode(4), TreeNode(5)
    # serStr = ser.serialize(root)
    # print(serStr)
    # res = deser.deserialize(serStr)
    # print(ser.serialize(res))

    ser = Codec2()
    deser = Codec2()
    root = TreeNode(1)
    root.left, root.right = TreeNode(2), TreeNode(3)
    root.right.left, root.right.right = TreeNode(4), TreeNode(5)
    serStr = ser.serialize(root)
    print(serStr)
    res = deser.deserialize(serStr)
    print(ser.serialize(res))
